<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN">
<HTML>
<HEAD>
<LINK REL=STYLESHEET TYPE="text/css" HREF="../stylesheet.css" TITLE="Style">
<META NAME="GENERATOR" CONTENT="Java2HTML Version 1.5">
<TITLE>jminusminus.NLinearRegisterAllocator (Java2HTML)</TITLE>
</HEAD>
<BODY><TABLE id="Header" border="0" cellpadding="0" cellspacing="0" width="100%">
<tr>
<td colspan="2" width="33%">&nbsp;</td>
<td align="center" colspan="2" width="33%">
<font size="4">NLinearRegisterAllocator.java</font>
</td>
<td align="right" colspan="2" width="33%">&nbsp;</td>
</tr>
</TABLE>
<pre ID="Classes">
<FONT ID="LN">1   </FONT><A NAME="1"></A><FONT ID="SingleLineComment">// Copyright 2013 Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
<FONT ID="LN">2   </FONT><A NAME="2"></A></FONT>
<FONT ID="LN">3   </FONT><A NAME="3"></A><FONT ID="Package">package</FONT> jminusminus;
<FONT ID="LN">4   </FONT><A NAME="4"></A>
<FONT ID="LN">5   </FONT><A NAME="5"></A><FONT ID="Import">import</FONT> java.util.ArrayList;
<FONT ID="LN">6   </FONT><A NAME="6"></A>
<FONT ID="LN">7   </FONT><A NAME="7"></A><FONT ID="FormalComment">/**
<FONT ID="LN">8   </FONT><A NAME="8"></A> * Implements the Linear Scan register allocation algorithm.
<FONT ID="LN">9   </FONT><A NAME="9"></A> */</FONT>
<FONT ID="LN">10  </FONT><A NAME="10"></A>
<FONT ID="LN">11  </FONT><A NAME="11"></A><FONT ID="Public">public</FONT> <FONT ID="Class">class</FONT> NLinearRegisterAllocator <FONT ID="Extends">extends</FONT> <A HREF="../jminusminus/NRegisterAllocator.java.html">NRegisterAllocator</A> {
<FONT ID="LN">12  </FONT><A NAME="12"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">13  </FONT><A NAME="13"></A>     * Interval queues for tracking the allocation process.
<FONT ID="LN">14  </FONT><A NAME="14"></A>     */</FONT>
<FONT ID="LN">15  </FONT><A NAME="15"></A>    <FONT ID="Private">private</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt; unhandled;
<FONT ID="LN">16  </FONT><A NAME="16"></A>    <FONT ID="Private">private</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt; active;
<FONT ID="LN">17  </FONT><A NAME="17"></A>    <FONT ID="Private">private</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt; inactive;
<FONT ID="LN">18  </FONT><A NAME="18"></A>
<FONT ID="LN">19  </FONT><A NAME="19"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">20  </FONT><A NAME="20"></A>     * Used to keep track of which intervals get assigned to what physical
<FONT ID="LN">21  </FONT><A NAME="21"></A>     * register. Needed only in allocateBlockedRegFor.
<FONT ID="LN">22  </FONT><A NAME="22"></A>     */</FONT>
<FONT ID="LN">23  </FONT><A NAME="23"></A>    <FONT ID="Private">private</FONT> ArrayList&lt;ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;&gt; regIntervals;
<FONT ID="LN">24  </FONT><A NAME="24"></A>    <FONT ID="Private">private</FONT> <FONT ID="Int">int</FONT>[] freePos, usePos, blockPos;
<FONT ID="LN">25  </FONT><A NAME="25"></A>
<FONT ID="LN">26  </FONT><A NAME="26"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">27  </FONT><A NAME="27"></A>     * Construct a linear register allocator for the given control flow graph.
<FONT ID="LN">28  </FONT><A NAME="28"></A>     * 
<FONT ID="LN">29  </FONT><A NAME="29"></A>     * @param cfg
<FONT ID="LN">30  </FONT><A NAME="30"></A>     *            the control flow graph instance.
<FONT ID="LN">31  </FONT><A NAME="31"></A>     */</FONT>
<FONT ID="LN">32  </FONT><A NAME="32"></A>
<FONT ID="LN">33  </FONT><A NAME="33"></A>    <FONT ID="Public">public</FONT> NLinearRegisterAllocator(<A HREF="../jminusminus/NControlFlowGraph.java.html">NControlFlowGraph</A> cfg) {
<FONT ID="LN">34  </FONT><A NAME="34"></A>        <FONT ID="Super">super</FONT>(cfg);
<FONT ID="LN">35  </FONT><A NAME="35"></A>        unhandled = <FONT ID="New">new</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;();
<FONT ID="LN">36  </FONT><A NAME="36"></A>        active = <FONT ID="New">new</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;();
<FONT ID="LN">37  </FONT><A NAME="37"></A>        inactive = <FONT ID="New">new</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;();
<FONT ID="LN">38  </FONT><A NAME="38"></A>
<FONT ID="LN">39  </FONT><A NAME="39"></A>        <FONT ID="SingleLineComment">// Instantiate usePositions and freePos to be the size of
<FONT ID="LN">40  </FONT><A NAME="40"></A></FONT>        <FONT ID="SingleLineComment">// the physical registers used.
<FONT ID="LN">41  </FONT><A NAME="41"></A></FONT>        freePos = <FONT ID="New">new</FONT> <FONT ID="Int">int</FONT>[NPhysicalRegister.MAX_COUNT];
<FONT ID="LN">42  </FONT><A NAME="42"></A>        usePos = <FONT ID="New">new</FONT> <FONT ID="Int">int</FONT>[NPhysicalRegister.MAX_COUNT];
<FONT ID="LN">43  </FONT><A NAME="43"></A>        blockPos = <FONT ID="New">new</FONT> <FONT ID="Int">int</FONT>[NPhysicalRegister.MAX_COUNT];
<FONT ID="LN">44  </FONT><A NAME="44"></A>        regIntervals = <FONT ID="New">new</FONT> ArrayList&lt;ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;&gt;();
<FONT ID="LN">45  </FONT><A NAME="45"></A>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; NPhysicalRegister.MAX_COUNT; i++) {
<FONT ID="LN">46  </FONT><A NAME="46"></A>            regIntervals.add(<FONT ID="New">new</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;());
<FONT ID="LN">47  </FONT><A NAME="47"></A>        }
<FONT ID="LN">48  </FONT><A NAME="48"></A>    }
<FONT ID="LN">49  </FONT><A NAME="49"></A>
<FONT ID="LN">50  </FONT><A NAME="50"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">51  </FONT><A NAME="51"></A>     * Perform the linear register allocation, assigning physical registers to
<FONT ID="LN">52  </FONT><A NAME="52"></A>     * virtual registers.
<FONT ID="LN">53  </FONT><A NAME="53"></A>     */</FONT>
<FONT ID="LN">54  </FONT><A NAME="54"></A>
<FONT ID="LN">55  </FONT><A NAME="55"></A>    <FONT ID="Public">public</FONT> <FONT ID="Void">void</FONT> allocation() {
<FONT ID="LN">56  </FONT><A NAME="56"></A>        <FONT ID="SingleLineComment">// Build the intervals for the control flow graph.
<FONT ID="LN">57  </FONT><A NAME="57"></A></FONT>        <FONT ID="This">this</FONT>.buildIntervals(); <FONT ID="SingleLineComment">// The correct intervals are now in intervals
<FONT ID="LN">58  </FONT><A NAME="58"></A></FONT>
<FONT ID="LN">59  </FONT><A NAME="59"></A>        <FONT ID="SingleLineComment">// Add all intervals corresponding to vregs to unhandled list
<FONT ID="LN">60  </FONT><A NAME="60"></A></FONT>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">32</FONT>; i &lt; cfg.intervals.size(); i++) {
<FONT ID="LN">61  </FONT><A NAME="61"></A>            <FONT ID="This">this</FONT>.addSortedToUnhandled(cfg.intervals.get(i));
<FONT ID="LN">62  </FONT><A NAME="62"></A>        }
<FONT ID="LN">63  </FONT><A NAME="63"></A>
<FONT ID="LN">64  </FONT><A NAME="64"></A>        <FONT ID="SingleLineComment">// Allocate any fixed registers (a0, ..., a3 and v0) that were
<FONT ID="LN">65  </FONT><A NAME="65"></A></FONT>        <FONT ID="SingleLineComment">// assigned during generation phase to the appropriate
<FONT ID="LN">66  </FONT><A NAME="66"></A></FONT>        <FONT ID="SingleLineComment">// interval.
<FONT ID="LN">67  </FONT><A NAME="67"></A></FONT>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; <FONT ID="IntegerLiteral">32</FONT>; i++) {
<FONT ID="LN">68  </FONT><A NAME="68"></A>            <FONT ID="If">if</FONT> (cfg.registers.get(i) != <FONT ID="Null">null</FONT>) {
<FONT ID="LN">69  </FONT><A NAME="69"></A>                cfg.intervals.get(i).pRegister = (NPhysicalRegister) cfg.registers
<FONT ID="LN">70  </FONT><A NAME="70"></A>                        .get(i);
<FONT ID="LN">71  </FONT><A NAME="71"></A>            }
<FONT ID="LN">72  </FONT><A NAME="72"></A>        }
<FONT ID="LN">73  </FONT><A NAME="73"></A>
<FONT ID="LN">74  </FONT><A NAME="74"></A>        <FONT ID="SingleLineComment">// Assign stack offset (relative to fp) for formal parameters
<FONT ID="LN">75  </FONT><A NAME="75"></A></FONT>        <FONT ID="SingleLineComment">// fourth and above, and stack offset (relative to sp) for
<FONT ID="LN">76  </FONT><A NAME="76"></A></FONT>        <FONT ID="SingleLineComment">// arguments fourth or above.
<FONT ID="LN">77  </FONT><A NAME="77"></A></FONT>        <FONT ID="For">for</FONT> (NBasicBlock block : cfg.basicBlocks) {
<FONT ID="LN">78  </FONT><A NAME="78"></A>            <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NLIRInstruction.java.html">NLIRInstruction</A> lir : block.lir) {
<FONT ID="LN">79  </FONT><A NAME="79"></A>                <FONT ID="If">if</FONT> (lir <FONT ID="InstanceOf">instanceof</FONT> NLIRLoadLocal) {
<FONT ID="LN">80  </FONT><A NAME="80"></A>                    NLIRLoadLocal loadLocal = (NLIRLoadLocal) lir;
<FONT ID="LN">81  </FONT><A NAME="81"></A>                    <FONT ID="If">if</FONT> (loadLocal.local &gt;= <FONT ID="IntegerLiteral">4</FONT>) {
<FONT ID="LN">82  </FONT><A NAME="82"></A>                        <A HREF="../jminusminus/NInterval.java.html">NInterval</A> interval = cfg.intervals
<FONT ID="LN">83  </FONT><A NAME="83"></A>                                .get(((NVirtualRegister) loadLocal.write)
<FONT ID="LN">84  </FONT><A NAME="84"></A>                                        .number());
<FONT ID="LN">85  </FONT><A NAME="85"></A>                        interval.spill = <FONT ID="True">true</FONT>;
<FONT ID="LN">86  </FONT><A NAME="86"></A>                        interval.offset = loadLocal.local - <FONT ID="IntegerLiteral">3</FONT>;
<FONT ID="LN">87  </FONT><A NAME="87"></A>                        interval.offsetFrom = OffsetFrom.FP;
<FONT ID="LN">88  </FONT><A NAME="88"></A>                    }
<FONT ID="LN">89  </FONT><A NAME="89"></A>                }
<FONT ID="LN">90  </FONT><A NAME="90"></A>            }
<FONT ID="LN">91  </FONT><A NAME="91"></A>        }
<FONT ID="LN">92  </FONT><A NAME="92"></A>
<FONT ID="LN">93  </FONT><A NAME="93"></A>        <A HREF="../jminusminus/NInterval.java.html">NInterval</A> currInterval; <FONT ID="SingleLineComment">// the current interval
<FONT ID="LN">94  </FONT><A NAME="94"></A></FONT>        <FONT ID="Int">int</FONT> psi; <FONT ID="SingleLineComment">// the current interval's first start position
<FONT ID="LN">95  </FONT><A NAME="95"></A></FONT>        ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt; tmp;
<FONT ID="LN">96  </FONT><A NAME="96"></A>
<FONT ID="LN">97  </FONT><A NAME="97"></A>        <FONT ID="SingleLineComment">// Linear allocation begins; repeat so long as there are
<FONT ID="LN">98  </FONT><A NAME="98"></A></FONT>        <FONT ID="SingleLineComment">// additional virtual registers to map to physical registers.
<FONT ID="LN">99  </FONT><A NAME="99"></A></FONT>        <FONT ID="While">while</FONT> (!unhandled.isEmpty()) {
<FONT ID="LN">100 </FONT><A NAME="100"></A>            currInterval = unhandled.remove(<FONT ID="IntegerLiteral">0</FONT>);
<FONT ID="LN">101 </FONT><A NAME="101"></A>            psi = currInterval.firstRangeStart();
<FONT ID="LN">102 </FONT><A NAME="102"></A>            tmp = <FONT ID="New">new</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;();
<FONT ID="LN">103 </FONT><A NAME="103"></A>            <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; active.size(); i++) {
<FONT ID="LN">104 </FONT><A NAME="104"></A>                <FONT ID="If">if</FONT> (active.get(i).lastNRangeStop() &lt; psi) {
<FONT ID="LN">105 </FONT><A NAME="105"></A>                    tmp.add(active.get(i));
<FONT ID="LN">106 </FONT><A NAME="106"></A>                } <FONT ID="Else">else</FONT> <FONT ID="If">if</FONT> (!active.get(i).isLiveAt(psi)) {
<FONT ID="LN">107 </FONT><A NAME="107"></A>                    inactive.add(active.get(i));
<FONT ID="LN">108 </FONT><A NAME="108"></A>                    tmp.add(active.get(i));
<FONT ID="LN">109 </FONT><A NAME="109"></A>                }
<FONT ID="LN">110 </FONT><A NAME="110"></A>            }
<FONT ID="LN">111 </FONT><A NAME="111"></A>            <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> nonActive : tmp) {
<FONT ID="LN">112 </FONT><A NAME="112"></A>                active.remove(nonActive);
<FONT ID="LN">113 </FONT><A NAME="113"></A>            }
<FONT ID="LN">114 </FONT><A NAME="114"></A>            tmp = <FONT ID="New">new</FONT> ArrayList&lt;<A HREF="../jminusminus/NInterval.java.html">NInterval</A>&gt;();
<FONT ID="LN">115 </FONT><A NAME="115"></A>            <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; inactive.size(); i++) {
<FONT ID="LN">116 </FONT><A NAME="116"></A>                <FONT ID="If">if</FONT> (inactive.get(i).lastNRangeStop() &lt; psi) {
<FONT ID="LN">117 </FONT><A NAME="117"></A>                    tmp.add(inactive.get(i));
<FONT ID="LN">118 </FONT><A NAME="118"></A>                } <FONT ID="Else">else</FONT> <FONT ID="If">if</FONT> (inactive.get(i).isLiveAt(psi)) {
<FONT ID="LN">119 </FONT><A NAME="119"></A>                    active.add(inactive.get(i));
<FONT ID="LN">120 </FONT><A NAME="120"></A>                    tmp.add(inactive.get(i));
<FONT ID="LN">121 </FONT><A NAME="121"></A>                }
<FONT ID="LN">122 </FONT><A NAME="122"></A>            }
<FONT ID="LN">123 </FONT><A NAME="123"></A>            <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> nonInActive : tmp) {
<FONT ID="LN">124 </FONT><A NAME="124"></A>                inactive.remove(nonInActive);
<FONT ID="LN">125 </FONT><A NAME="125"></A>            }
<FONT ID="LN">126 </FONT><A NAME="126"></A>            <FONT ID="If">if</FONT> (!<FONT ID="This">this</FONT>.foundFreeRegFor(currInterval)) {<FONT ID="SingleLineComment">// check
<FONT ID="LN">127 </FONT><A NAME="127"></A></FONT>                <FONT ID="This">this</FONT>.allocateBlockedRegFor(currInterval); <FONT ID="SingleLineComment">// never fails
<FONT ID="LN">128 </FONT><A NAME="128"></A></FONT>            }
<FONT ID="LN">129 </FONT><A NAME="129"></A>            active.add(currInterval);
<FONT ID="LN">130 </FONT><A NAME="130"></A>        }
<FONT ID="LN">131 </FONT><A NAME="131"></A>        <FONT ID="This">this</FONT>.resolveDataFlow();
<FONT ID="LN">132 </FONT><A NAME="132"></A>    }
<FONT ID="LN">133 </FONT><A NAME="133"></A>
<FONT ID="LN">134 </FONT><A NAME="134"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">135 </FONT><A NAME="135"></A>     * Adds a given interval onto the unhandled list, maintaining an order based
<FONT ID="LN">136 </FONT><A NAME="136"></A>     * on the first range start of the NIntervals.
<FONT ID="LN">137 </FONT><A NAME="137"></A>     * 
<FONT ID="LN">138 </FONT><A NAME="138"></A>     * @param newInterval
<FONT ID="LN">139 </FONT><A NAME="139"></A>     *            the NInterval to sort onto unhandled.
<FONT ID="LN">140 </FONT><A NAME="140"></A>     */</FONT>
<FONT ID="LN">141 </FONT><A NAME="141"></A>
<FONT ID="LN">142 </FONT><A NAME="142"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> addSortedToUnhandled(<A HREF="../jminusminus/NInterval.java.html">NInterval</A> newInterval) {
<FONT ID="LN">143 </FONT><A NAME="143"></A>        <FONT ID="If">if</FONT> (unhandled.isEmpty()) {
<FONT ID="LN">144 </FONT><A NAME="144"></A>            unhandled.add(newInterval);
<FONT ID="LN">145 </FONT><A NAME="145"></A>        } <FONT ID="Else">else</FONT> {
<FONT ID="LN">146 </FONT><A NAME="146"></A>            <FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>;
<FONT ID="LN">147 </FONT><A NAME="147"></A>            <FONT ID="While">while</FONT> (i &lt; unhandled.size()
<FONT ID="LN">148 </FONT><A NAME="148"></A>                    &amp;&amp; unhandled.get(i).firstRangeStart() &lt;= newInterval
<FONT ID="LN">149 </FONT><A NAME="149"></A>                            .firstRangeStart()) {
<FONT ID="LN">150 </FONT><A NAME="150"></A>                i++;
<FONT ID="LN">151 </FONT><A NAME="151"></A>            }
<FONT ID="LN">152 </FONT><A NAME="152"></A>            unhandled.add(i, newInterval);
<FONT ID="LN">153 </FONT><A NAME="153"></A>        }
<FONT ID="LN">154 </FONT><A NAME="154"></A>    }
<FONT ID="LN">155 </FONT><A NAME="155"></A>
<FONT ID="LN">156 </FONT><A NAME="156"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">157 </FONT><A NAME="157"></A>     * Allocates a free physical register for the current interval. Inspects
<FONT ID="LN">158 </FONT><A NAME="158"></A>     * active and inactive sets. Cannot split or alter the assigned physical
<FONT ID="LN">159 </FONT><A NAME="159"></A>     * register of any other interval but current.
<FONT ID="LN">160 </FONT><A NAME="160"></A>     * 
<FONT ID="LN">161 </FONT><A NAME="161"></A>     * @param currInterval
<FONT ID="LN">162 </FONT><A NAME="162"></A>     *            the current interval for which a physical register is sought.
<FONT ID="LN">163 </FONT><A NAME="163"></A>     * @return true if a free physical register was found and allocated for
<FONT ID="LN">164 </FONT><A NAME="164"></A>     *         currInterval, false otherwise.
<FONT ID="LN">165 </FONT><A NAME="165"></A>     */</FONT>
<FONT ID="LN">166 </FONT><A NAME="166"></A>
<FONT ID="LN">167 </FONT><A NAME="167"></A>    <FONT ID="Private">private</FONT> <FONT ID="Boolean">boolean</FONT> foundFreeRegFor(<A HREF="../jminusminus/NInterval.java.html">NInterval</A> currInterval) {
<FONT ID="LN">168 </FONT><A NAME="168"></A>        <FONT ID="This">this</FONT>.initFreePositions(); <FONT ID="SingleLineComment">// must be reset every iteration
<FONT ID="LN">169 </FONT><A NAME="169"></A></FONT>        <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> activeInterval : active) {
<FONT ID="LN">170 </FONT><A NAME="170"></A>            <FONT ID="If">if</FONT> (activeInterval.pRegister != <FONT ID="Null">null</FONT>)
<FONT ID="LN">171 </FONT><A NAME="171"></A>                freePos[activeInterval.pRegister.number - NPhysicalRegister.T0] = <FONT ID="IntegerLiteral">0</FONT>;
<FONT ID="LN">172 </FONT><A NAME="172"></A>        }
<FONT ID="LN">173 </FONT><A NAME="173"></A>        <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> inactiveInterval : inactive) {
<FONT ID="LN">174 </FONT><A NAME="174"></A>            <FONT ID="If">if</FONT> (inactiveInterval.nextIntersection(currInterval) &gt;= <FONT ID="IntegerLiteral">0</FONT>)
<FONT ID="LN">175 </FONT><A NAME="175"></A>                freePos[inactiveInterval.pRegister.number
<FONT ID="LN">176 </FONT><A NAME="176"></A>                        - NPhysicalRegister.T0] = Math.min(
<FONT ID="LN">177 </FONT><A NAME="177"></A>                        freePos[inactiveInterval.pRegister.number
<FONT ID="LN">178 </FONT><A NAME="178"></A>                                - NPhysicalRegister.T0], inactiveInterval
<FONT ID="LN">179 </FONT><A NAME="179"></A>                                .nextIntersection(currInterval));
<FONT ID="LN">180 </FONT><A NAME="180"></A>        }
<FONT ID="LN">181 </FONT><A NAME="181"></A>
<FONT ID="LN">182 </FONT><A NAME="182"></A>        <FONT ID="SingleLineComment">// The physical registers available are in NPhysicalRegister.getInfo
<FONT ID="LN">183 </FONT><A NAME="183"></A></FONT>        <FONT ID="SingleLineComment">// static array. This is indexed from 0 to NPhysicalRegister.MAX_COUNT
<FONT ID="LN">184 </FONT><A NAME="184"></A></FONT>        <FONT ID="Int">int</FONT> reg = <FONT ID="This">this</FONT>.getBestFreeReg();
<FONT ID="LN">185 </FONT><A NAME="185"></A>        <FONT ID="If">if</FONT> (freePos[reg] == <FONT ID="IntegerLiteral">0</FONT>)
<FONT ID="LN">186 </FONT><A NAME="186"></A>            <FONT ID="Return">return</FONT> <FONT ID="False">false</FONT>;
<FONT ID="LN">187 </FONT><A NAME="187"></A>        <FONT ID="Else">else</FONT> <FONT ID="If">if</FONT> (freePos[reg] &gt; currInterval.lastNRangeStop()) {
<FONT ID="LN">188 </FONT><A NAME="188"></A>            currInterval.pRegister = NPhysicalRegister.regInfo[reg
<FONT ID="LN">189 </FONT><A NAME="189"></A>                    + NPhysicalRegister.T0];
<FONT ID="LN">190 </FONT><A NAME="190"></A>            cfg.pRegisters.add(NPhysicalRegister.regInfo[reg
<FONT ID="LN">191 </FONT><A NAME="191"></A>                    + NPhysicalRegister.T0]);
<FONT ID="LN">192 </FONT><A NAME="192"></A>            regIntervals.get(reg).add(currInterval);
<FONT ID="LN">193 </FONT><A NAME="193"></A>            <FONT ID="Return">return</FONT> <FONT ID="True">true</FONT>;
<FONT ID="LN">194 </FONT><A NAME="194"></A>        } <FONT ID="Else">else</FONT> {
<FONT ID="LN">195 </FONT><A NAME="195"></A>            <FONT ID="This">this</FONT>.addSortedToUnhandled(currInterval.splitAt(freePos[reg]));
<FONT ID="LN">196 </FONT><A NAME="196"></A>            currInterval.spill();
<FONT ID="LN">197 </FONT><A NAME="197"></A>            currInterval.pRegister = NPhysicalRegister.regInfo[reg
<FONT ID="LN">198 </FONT><A NAME="198"></A>                    + NPhysicalRegister.T0];
<FONT ID="LN">199 </FONT><A NAME="199"></A>            regIntervals.get(reg).add(currInterval);
<FONT ID="LN">200 </FONT><A NAME="200"></A>            <FONT ID="Return">return</FONT> <FONT ID="True">true</FONT>;
<FONT ID="LN">201 </FONT><A NAME="201"></A>        }
<FONT ID="LN">202 </FONT><A NAME="202"></A>    }
<FONT ID="LN">203 </FONT><A NAME="203"></A>
<FONT ID="LN">204 </FONT><A NAME="204"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">205 </FONT><A NAME="205"></A>     * Sets all free positions of pregisters available for allocation to a
<FONT ID="LN">206 </FONT><A NAME="206"></A>     * really high number.
<FONT ID="LN">207 </FONT><A NAME="207"></A>     */</FONT>
<FONT ID="LN">208 </FONT><A NAME="208"></A>
<FONT ID="LN">209 </FONT><A NAME="209"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> initFreePositions() {
<FONT ID="LN">210 </FONT><A NAME="210"></A>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; NPhysicalRegister.MAX_COUNT; i++) {
<FONT ID="LN">211 </FONT><A NAME="211"></A>            freePos[i] = Integer.MAX_VALUE;
<FONT ID="LN">212 </FONT><A NAME="212"></A>        }
<FONT ID="LN">213 </FONT><A NAME="213"></A>    }
<FONT ID="LN">214 </FONT><A NAME="214"></A>
<FONT ID="LN">215 </FONT><A NAME="215"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">216 </FONT><A NAME="216"></A>     * The best free physical register.
<FONT ID="LN">217 </FONT><A NAME="217"></A>     * 
<FONT ID="LN">218 </FONT><A NAME="218"></A>     * @return the register number.
<FONT ID="LN">219 </FONT><A NAME="219"></A>     */</FONT>
<FONT ID="LN">220 </FONT><A NAME="220"></A>
<FONT ID="LN">221 </FONT><A NAME="221"></A>    <FONT ID="Private">private</FONT> <FONT ID="Int">int</FONT> getBestFreeReg() {
<FONT ID="LN">222 </FONT><A NAME="222"></A>        <FONT ID="Int">int</FONT> freeRegNumber = <FONT ID="IntegerLiteral">0</FONT>;
<FONT ID="LN">223 </FONT><A NAME="223"></A>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; NPhysicalRegister.MAX_COUNT; i++) {
<FONT ID="LN">224 </FONT><A NAME="224"></A>            <FONT ID="If">if</FONT> (freePos[i] &gt; freePos[freeRegNumber])
<FONT ID="LN">225 </FONT><A NAME="225"></A>                freeRegNumber = i;
<FONT ID="LN">226 </FONT><A NAME="226"></A>        }
<FONT ID="LN">227 </FONT><A NAME="227"></A>        <FONT ID="Return">return</FONT> freeRegNumber;
<FONT ID="LN">228 </FONT><A NAME="228"></A>    }
<FONT ID="LN">229 </FONT><A NAME="229"></A>
<FONT ID="LN">230 </FONT><A NAME="230"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">231 </FONT><A NAME="231"></A>     * Allocates a register based on spilling an interval.
<FONT ID="LN">232 </FONT><A NAME="232"></A>     * 
<FONT ID="LN">233 </FONT><A NAME="233"></A>     * @param currInterval
<FONT ID="LN">234 </FONT><A NAME="234"></A>     *            the current interval.
<FONT ID="LN">235 </FONT><A NAME="235"></A>     */</FONT>
<FONT ID="LN">236 </FONT><A NAME="236"></A>
<FONT ID="LN">237 </FONT><A NAME="237"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> allocateBlockedRegFor(<A HREF="../jminusminus/NInterval.java.html">NInterval</A> currInterval) {
<FONT ID="LN">238 </FONT><A NAME="238"></A>        <FONT ID="This">this</FONT>.initUseAndBlockPositions(); <FONT ID="SingleLineComment">// must be reset every iteration
<FONT ID="LN">239 </FONT><A NAME="239"></A></FONT>        <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> activeInterval : active) {
<FONT ID="LN">240 </FONT><A NAME="240"></A>            usePos[activeInterval.pRegister.number - NPhysicalRegister.T0] = Math
<FONT ID="LN">241 </FONT><A NAME="241"></A>                    .min(usePos[activeInterval.pRegister.number
<FONT ID="LN">242 </FONT><A NAME="242"></A>                            - NPhysicalRegister.T0], activeInterval
<FONT ID="LN">243 </FONT><A NAME="243"></A>                            .nextUsageOverlapping(currInterval));
<FONT ID="LN">244 </FONT><A NAME="244"></A>        }
<FONT ID="LN">245 </FONT><A NAME="245"></A>        <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> inactiveInterval : inactive) {
<FONT ID="LN">246 </FONT><A NAME="246"></A>            <FONT ID="If">if</FONT> (inactiveInterval.nextIntersection(currInterval) &gt;= <FONT ID="IntegerLiteral">0</FONT>)
<FONT ID="LN">247 </FONT><A NAME="247"></A>                usePos[inactiveInterval.pRegister.number - NPhysicalRegister.T0] = Math
<FONT ID="LN">248 </FONT><A NAME="248"></A>                        .min(usePos[inactiveInterval.pRegister.number
<FONT ID="LN">249 </FONT><A NAME="249"></A>                                - NPhysicalRegister.T0], inactiveInterval
<FONT ID="LN">250 </FONT><A NAME="250"></A>                                .nextUsageOverlapping(currInterval));
<FONT ID="LN">251 </FONT><A NAME="251"></A>        }
<FONT ID="LN">252 </FONT><A NAME="252"></A>        <FONT ID="Int">int</FONT> reg = <FONT ID="This">this</FONT>.getBestBlockedReg(); <FONT ID="SingleLineComment">// this is just an index in the
<FONT ID="LN">253 </FONT><A NAME="253"></A></FONT>        <FONT ID="SingleLineComment">// usePos array
<FONT ID="LN">254 </FONT><A NAME="254"></A></FONT>        <FONT ID="If">if</FONT> (usePos[reg] &lt; currInterval.firstUsage()) {
<FONT ID="LN">255 </FONT><A NAME="255"></A>            <FONT ID="SingleLineComment">// best to spill current - no reg assignment.
<FONT ID="LN">256 </FONT><A NAME="256"></A></FONT>            <FONT ID="This">this</FONT>.addSortedToUnhandled(currInterval.splitAt(currInterval
<FONT ID="LN">257 </FONT><A NAME="257"></A>                    .firstUsage() - <FONT ID="IntegerLiteral">5</FONT>));
<FONT ID="LN">258 </FONT><A NAME="258"></A>            currInterval.spill();
<FONT ID="LN">259 </FONT><A NAME="259"></A>            <A HREF="../jminusminus/NInterval.java.html">NInterval</A> splitChild = currInterval.splitAt(currInterval
<FONT ID="LN">260 </FONT><A NAME="260"></A>                    .firstRangeStart());
<FONT ID="LN">261 </FONT><A NAME="261"></A>            <FONT ID="This">this</FONT>.addSortedToUnhandled(splitChild);
<FONT ID="LN">262 </FONT><A NAME="262"></A>            currInterval.spill();
<FONT ID="LN">263 </FONT><A NAME="263"></A>        } <FONT ID="Else">else</FONT> {
<FONT ID="LN">264 </FONT><A NAME="264"></A>            <FONT ID="SingleLineComment">// spilling frees reg for all of current
<FONT ID="LN">265 </FONT><A NAME="265"></A></FONT>            currInterval.pRegister = NPhysicalRegister.regInfo[reg
<FONT ID="LN">266 </FONT><A NAME="266"></A>                    + NPhysicalRegister.T0];
<FONT ID="LN">267 </FONT><A NAME="267"></A>            <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> i : regIntervals.get(reg)) {
<FONT ID="LN">268 </FONT><A NAME="268"></A>                <FONT ID="If">if</FONT> (currInterval.nextIntersection(i) &gt;= <FONT ID="IntegerLiteral">0</FONT>) {
<FONT ID="LN">269 </FONT><A NAME="269"></A>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> splitChild = i.splitAt(currInterval
<FONT ID="LN">270 </FONT><A NAME="270"></A>                            .firstRangeStart());
<FONT ID="LN">271 </FONT><A NAME="271"></A>                    <FONT ID="This">this</FONT>.addSortedToUnhandled(splitChild);
<FONT ID="LN">272 </FONT><A NAME="272"></A>                    i.spill();
<FONT ID="LN">273 </FONT><A NAME="273"></A>                }
<FONT ID="LN">274 </FONT><A NAME="274"></A>            }
<FONT ID="LN">275 </FONT><A NAME="275"></A>            regIntervals.get(reg).add(currInterval);
<FONT ID="LN">276 </FONT><A NAME="276"></A>        }
<FONT ID="LN">277 </FONT><A NAME="277"></A>    }
<FONT ID="LN">278 </FONT><A NAME="278"></A>
<FONT ID="LN">279 </FONT><A NAME="279"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">280 </FONT><A NAME="280"></A>     * Initialize use and block positions before processing each virtual
<FONT ID="LN">281 </FONT><A NAME="281"></A>     * rgister.
<FONT ID="LN">282 </FONT><A NAME="282"></A>     */</FONT>
<FONT ID="LN">283 </FONT><A NAME="283"></A>
<FONT ID="LN">284 </FONT><A NAME="284"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> initUseAndBlockPositions() {
<FONT ID="LN">285 </FONT><A NAME="285"></A>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; NPhysicalRegister.MAX_COUNT; i++) {
<FONT ID="LN">286 </FONT><A NAME="286"></A>            usePos[i] = Integer.MAX_VALUE;
<FONT ID="LN">287 </FONT><A NAME="287"></A>            blockPos[i] = Integer.MAX_VALUE;
<FONT ID="LN">288 </FONT><A NAME="288"></A>        }
<FONT ID="LN">289 </FONT><A NAME="289"></A>    }
<FONT ID="LN">290 </FONT><A NAME="290"></A>
<FONT ID="LN">291 </FONT><A NAME="291"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">292 </FONT><A NAME="292"></A>     * Get the best blocked physical register.
<FONT ID="LN">293 </FONT><A NAME="293"></A>     * 
<FONT ID="LN">294 </FONT><A NAME="294"></A>     * @return the register number.
<FONT ID="LN">295 </FONT><A NAME="295"></A>     */</FONT>
<FONT ID="LN">296 </FONT><A NAME="296"></A>
<FONT ID="LN">297 </FONT><A NAME="297"></A>    <FONT ID="Private">private</FONT> <FONT ID="Int">int</FONT> getBestBlockedReg() {
<FONT ID="LN">298 </FONT><A NAME="298"></A>        <FONT ID="Int">int</FONT> usableRegNumber = <FONT ID="IntegerLiteral">0</FONT>;
<FONT ID="LN">299 </FONT><A NAME="299"></A>        <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = <FONT ID="IntegerLiteral">0</FONT>; i &lt; NPhysicalRegister.MAX_COUNT; i++) {
<FONT ID="LN">300 </FONT><A NAME="300"></A>            <FONT ID="If">if</FONT> (usePos[i] &gt; usePos[usableRegNumber])
<FONT ID="LN">301 </FONT><A NAME="301"></A>                usableRegNumber = i;
<FONT ID="LN">302 </FONT><A NAME="302"></A>        }
<FONT ID="LN">303 </FONT><A NAME="303"></A>        <FONT ID="Return">return</FONT> usableRegNumber;
<FONT ID="LN">304 </FONT><A NAME="304"></A>    }
<FONT ID="LN">305 </FONT><A NAME="305"></A>
<FONT ID="LN">306 </FONT><A NAME="306"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">307 </FONT><A NAME="307"></A>     * Resolve the data flow after allocating registers, inserting additional
<FONT ID="LN">308 </FONT><A NAME="308"></A>     * saves and restores for registers to maintain consistency.
<FONT ID="LN">309 </FONT><A NAME="309"></A>     */</FONT>
<FONT ID="LN">310 </FONT><A NAME="310"></A>
<FONT ID="LN">311 </FONT><A NAME="311"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> resolveDataFlow() {
<FONT ID="LN">312 </FONT><A NAME="312"></A>        <FONT ID="SingleLineComment">// local data flow construction
<FONT ID="LN">313 </FONT><A NAME="313"></A></FONT>        <FONT ID="SingleLineComment">// Devised an alternate way of doing this, perhaps with more
<FONT ID="LN">314 </FONT><A NAME="314"></A></FONT>        <FONT ID="SingleLineComment">// clarity, will implement later, but has same effect.
<FONT ID="LN">315 </FONT><A NAME="315"></A></FONT>        <FONT ID="For">for</FONT> (<A HREF="../jminusminus/NInterval.java.html">NInterval</A> i : cfg.intervals) {
<FONT ID="LN">316 </FONT><A NAME="316"></A>            <FONT ID="If">if</FONT> (cfg.registers.get(i.vRegId) != <FONT ID="Null">null</FONT>) {
<FONT ID="LN">317 </FONT><A NAME="317"></A>                <FONT ID="If">if</FONT> (i.spill) {
<FONT ID="LN">318 </FONT><A NAME="318"></A>                    <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> c = <FONT ID="IntegerLiteral">0</FONT>; c &lt; i.children.size(); c++) {
<FONT ID="LN">319 </FONT><A NAME="319"></A>                        <FONT ID="If">if</FONT> (i.endsAtBlock() == i.children.get(c)
<FONT ID="LN">320 </FONT><A NAME="320"></A>                                .startsAtBlock()) {
<FONT ID="LN">321 </FONT><A NAME="321"></A>                            <FONT ID="If">if</FONT> (c == <FONT ID="IntegerLiteral">0</FONT>) {
<FONT ID="LN">322 </FONT><A NAME="322"></A>                                addStoreInstruction(i, i.lastNRangeStop());
<FONT ID="LN">323 </FONT><A NAME="323"></A>                                addLoadInstruction(i.children.get(c),
<FONT ID="LN">324 </FONT><A NAME="324"></A>                                        i.children.get(c).firstRangeStart());
<FONT ID="LN">325 </FONT><A NAME="325"></A>                            } <FONT ID="Else">else</FONT> {
<FONT ID="LN">326 </FONT><A NAME="326"></A>                                addStoreInstruction(i.children.get(c - <FONT ID="IntegerLiteral">1</FONT>),
<FONT ID="LN">327 </FONT><A NAME="327"></A>                                        i.children.get(c - <FONT ID="IntegerLiteral">1</FONT>).lastNRangeStop());
<FONT ID="LN">328 </FONT><A NAME="328"></A>                                addLoadInstruction(i.children.get(c),
<FONT ID="LN">329 </FONT><A NAME="329"></A>                                        i.children.get(c).firstRangeStart());
<FONT ID="LN">330 </FONT><A NAME="330"></A>                            }
<FONT ID="LN">331 </FONT><A NAME="331"></A>                        }
<FONT ID="LN">332 </FONT><A NAME="332"></A>                    }
<FONT ID="LN">333 </FONT><A NAME="333"></A>                }
<FONT ID="LN">334 </FONT><A NAME="334"></A>            }
<FONT ID="LN">335 </FONT><A NAME="335"></A>        }
<FONT ID="LN">336 </FONT><A NAME="336"></A>
<FONT ID="LN">337 </FONT><A NAME="337"></A>        <FONT ID="SingleLineComment">// resolution of global data flow
<FONT ID="LN">338 </FONT><A NAME="338"></A></FONT>        <FONT ID="For">for</FONT> (NBasicBlock b : cfg.basicBlocks) {
<FONT ID="LN">339 </FONT><A NAME="339"></A>            <FONT ID="For">for</FONT> (NBasicBlock s : b.successors) {
<FONT ID="LN">340 </FONT><A NAME="340"></A>                <FONT ID="For">for</FONT> (<FONT ID="Int">int</FONT> i = s.liveIn.nextSetBit(<FONT ID="IntegerLiteral">0</FONT>); i &gt;= <FONT ID="IntegerLiteral">0</FONT>; i = s.liveIn
<FONT ID="LN">341 </FONT><A NAME="341"></A>                        .nextSetBit(i + <FONT ID="IntegerLiteral">1</FONT>)) {
<FONT ID="LN">342 </FONT><A NAME="342"></A>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> parent = cfg.intervals.get(i);
<FONT ID="LN">343 </FONT><A NAME="343"></A>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> from = parent.childAtOrEndingBefore(b);
<FONT ID="LN">344 </FONT><A NAME="344"></A>                    <A HREF="../jminusminus/NInterval.java.html">NInterval</A> to = parent.childAtOrStartingAfter(s);
<FONT ID="LN">345 </FONT><A NAME="345"></A>                    <FONT ID="If">if</FONT> (!from.equals(to)) {
<FONT ID="LN">346 </FONT><A NAME="346"></A>                        addStoreInstruction(from, from.usePositions.floorKey(b
<FONT ID="LN">347 </FONT><A NAME="347"></A>                                .getLastLIRInstId()));
<FONT ID="LN">348 </FONT><A NAME="348"></A>                        to = getSegmentWithNearestUse(to, s.getFirstLIRInstId());
<FONT ID="LN">349 </FONT><A NAME="349"></A>                        <FONT ID="If">if</FONT> (to.usePositions.ceilingEntry(s.getFirstLIRInstId())
<FONT ID="LN">350 </FONT><A NAME="350"></A>                                .getValue() == InstructionType.read)
<FONT ID="LN">351 </FONT><A NAME="351"></A>                            <FONT ID="SingleLineComment">// no use loading prior to a write.
<FONT ID="LN">352 </FONT><A NAME="352"></A></FONT>                            addLoadInstruction(to, to.usePositions.ceilingKey(s
<FONT ID="LN">353 </FONT><A NAME="353"></A>                                    .getFirstLIRInstId()));
<FONT ID="LN">354 </FONT><A NAME="354"></A>                    }
<FONT ID="LN">355 </FONT><A NAME="355"></A>                }
<FONT ID="LN">356 </FONT><A NAME="356"></A>            }
<FONT ID="LN">357 </FONT><A NAME="357"></A>        }
<FONT ID="LN">358 </FONT><A NAME="358"></A>    }
<FONT ID="LN">359 </FONT><A NAME="359"></A>
<FONT ID="LN">360 </FONT><A NAME="360"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">361 </FONT><A NAME="361"></A>     * Get the the interval segment that contains the nearest first use.
<FONT ID="LN">362 </FONT><A NAME="362"></A>     * 
<FONT ID="LN">363 </FONT><A NAME="363"></A>     * @param i
<FONT ID="LN">364 </FONT><A NAME="364"></A>     *            the interval segment (could be a parent or child).
<FONT ID="LN">365 </FONT><A NAME="365"></A>     * @param id
<FONT ID="LN">366 </FONT><A NAME="366"></A>     *            the lir id after which a use is sought.
<FONT ID="LN">367 </FONT><A NAME="367"></A>     * @return the interval segment that that contains the first use at or after
<FONT ID="LN">368 </FONT><A NAME="368"></A>     *         the id position and is associated with the interval i through a
<FONT ID="LN">369 </FONT><A NAME="369"></A>     *         sibling or child relationship. Returns i if there is a use after
<FONT ID="LN">370 </FONT><A NAME="370"></A>     *         id within i. Null if no interval exists that is related to i and
<FONT ID="LN">371 </FONT><A NAME="371"></A>     *         contains a use position at or after id.
<FONT ID="LN">372 </FONT><A NAME="372"></A>     */</FONT>
<FONT ID="LN">373 </FONT><A NAME="373"></A>
<FONT ID="LN">374 </FONT><A NAME="374"></A>    <FONT ID="Private">private</FONT> <A HREF="../jminusminus/NInterval.java.html">NInterval</A> getSegmentWithNearestUse(<A HREF="../jminusminus/NInterval.java.html">NInterval</A> i, <FONT ID="Int">int</FONT> id) {
<FONT ID="LN">375 </FONT><A NAME="375"></A>        <FONT ID="If">if</FONT> (i.usePositions.ceilingEntry(id) != <FONT ID="Null">null</FONT>)
<FONT ID="LN">376 </FONT><A NAME="376"></A>            <FONT ID="Return">return</FONT> i;
<FONT ID="LN">377 </FONT><A NAME="377"></A>        <FONT ID="Else">else</FONT> {
<FONT ID="LN">378 </FONT><A NAME="378"></A>            <A HREF="../jminusminus/NInterval.java.html">NInterval</A> parent = i;
<FONT ID="LN">379 </FONT><A NAME="379"></A>            <FONT ID="Int">int</FONT> idx = <FONT ID="IntegerLiteral">0</FONT>;
<FONT ID="LN">380 </FONT><A NAME="380"></A>            <FONT ID="If">if</FONT> (i.isChild()) {
<FONT ID="LN">381 </FONT><A NAME="381"></A>                parent = i.parent;
<FONT ID="LN">382 </FONT><A NAME="382"></A>                idx = parent.children.indexOf(i) + <FONT ID="IntegerLiteral">1</FONT>;
<FONT ID="LN">383 </FONT><A NAME="383"></A>            }
<FONT ID="LN">384 </FONT><A NAME="384"></A>            <FONT ID="For">for</FONT> (; idx &lt; parent.children.size(); idx++) {
<FONT ID="LN">385 </FONT><A NAME="385"></A>                <FONT ID="If">if</FONT> (parent.children.get(idx).usePositions.ceilingEntry(id) != <FONT ID="Null">null</FONT>)
<FONT ID="LN">386 </FONT><A NAME="386"></A>                    <FONT ID="Return">return</FONT> parent.children.get(idx);
<FONT ID="LN">387 </FONT><A NAME="387"></A>            }
<FONT ID="LN">388 </FONT><A NAME="388"></A>            <FONT ID="Return">return</FONT> <FONT ID="Null">null</FONT>;
<FONT ID="LN">389 </FONT><A NAME="389"></A>        }
<FONT ID="LN">390 </FONT><A NAME="390"></A>    }
<FONT ID="LN">391 </FONT><A NAME="391"></A>
<FONT ID="LN">392 </FONT><A NAME="392"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">393 </FONT><A NAME="393"></A>     * Adds a store instruction right after a use position specified by id.
<FONT ID="LN">394 </FONT><A NAME="394"></A>     * 
<FONT ID="LN">395 </FONT><A NAME="395"></A>     * @param from
<FONT ID="LN">396 </FONT><A NAME="396"></A>     *            the interval which this use position is a part of.
<FONT ID="LN">397 </FONT><A NAME="397"></A>     * @param id
<FONT ID="LN">398 </FONT><A NAME="398"></A>     *            the id of the use position.
<FONT ID="LN">399 </FONT><A NAME="399"></A>     */</FONT>
<FONT ID="LN">400 </FONT><A NAME="400"></A>
<FONT ID="LN">401 </FONT><A NAME="401"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> addStoreInstruction(<A HREF="../jminusminus/NInterval.java.html">NInterval</A> from, <FONT ID="Int">int</FONT> id) {
<FONT ID="LN">402 </FONT><A NAME="402"></A>        NBasicBlock b = cfg.blockAt(id);
<FONT ID="LN">403 </FONT><A NAME="403"></A>        id++;
<FONT ID="LN">404 </FONT><A NAME="404"></A>        <FONT ID="If">if</FONT> (b.idIsFree(id)) { <FONT ID="SingleLineComment">// assumes always same instr
<FONT ID="LN">405 </FONT><A NAME="405"></A></FONT>            b.insertLIRInst(<FONT ID="New">new</FONT> NLIRStore(b, id, from.offset, from.offsetFrom,
<FONT ID="LN">406 </FONT><A NAME="406"></A>                    from.pRegister));
<FONT ID="LN">407 </FONT><A NAME="407"></A>        }
<FONT ID="LN">408 </FONT><A NAME="408"></A>    }
<FONT ID="LN">409 </FONT><A NAME="409"></A>
<FONT ID="LN">410 </FONT><A NAME="410"></A>    <FONT ID="FormalComment">/**
<FONT ID="LN">411 </FONT><A NAME="411"></A>     * Adds a store instruction right before a use position specified by id.
<FONT ID="LN">412 </FONT><A NAME="412"></A>     * 
<FONT ID="LN">413 </FONT><A NAME="413"></A>     * @param to
<FONT ID="LN">414 </FONT><A NAME="414"></A>     *            the interval which this use position is a part of.
<FONT ID="LN">415 </FONT><A NAME="415"></A>     * @param id
<FONT ID="LN">416 </FONT><A NAME="416"></A>     *            the id of the use position.
<FONT ID="LN">417 </FONT><A NAME="417"></A>     */</FONT>
<FONT ID="LN">418 </FONT><A NAME="418"></A>
<FONT ID="LN">419 </FONT><A NAME="419"></A>    <FONT ID="Private">private</FONT> <FONT ID="Void">void</FONT> addLoadInstruction(<A HREF="../jminusminus/NInterval.java.html">NInterval</A> to, <FONT ID="Int">int</FONT> id) {
<FONT ID="LN">420 </FONT><A NAME="420"></A>        NBasicBlock s = cfg.blockAt(id);
<FONT ID="LN">421 </FONT><A NAME="421"></A>        id--;
<FONT ID="LN">422 </FONT><A NAME="422"></A>        <FONT ID="If">if</FONT> (s.idIsFree(id)) { <FONT ID="SingleLineComment">// assumes always same instr
<FONT ID="LN">423 </FONT><A NAME="423"></A></FONT>            s.insertLIRInst(<FONT ID="New">new</FONT> NLIRLoad(s, id, to.offset, to.offsetFrom,
<FONT ID="LN">424 </FONT><A NAME="424"></A>                    to.pRegister));
<FONT ID="LN">425 </FONT><A NAME="425"></A>        }
<FONT ID="LN">426 </FONT><A NAME="426"></A>    }
<FONT ID="LN">427 </FONT><A NAME="427"></A>
<FONT ID="LN">428 </FONT><A NAME="428"></A>}</pre>
</BODY>
</HTML>